import java.util.ArrayList;
import java.util.List;

public class Solution17 {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        dfs(res, cur, digits);
        return res;
    }

    private void dfs(List<String> res, StringBuilder cur, String str) {
        if (str.length() == 0) {
            if (cur.length() > 0) {
                res.add(String.valueOf(cur));
                cur.deleteCharAt(cur.length() - 1);
            }
            return;
        }
        int digit = Integer.parseInt(str.substring(0, 1));
        if (digit < 7) {
            for (int i = 0; i < 3; i++) {
                char c = (char) ((digit - 2) * 3 + i + 'a');
                dfs(res, cur.append(c), str.substring(1));
            }
        } else if (digit == 7) {
            for (int i = 0; i < 4; i++) {
                char c = (char) (i + 'p');
                dfs(res, cur.append(c), str.substring(1));
            }
        } else if (digit == 8) {
            for (int i = 0; i < 3; i++) {
                char c = (char) ('t' + i);
                dfs(res, cur.append(c), str.substring(1));
            }
        } else {
            for (int i = 0; i < 4; i++) {
                char c = (char) ('w' + i);
                dfs(res, cur.append(c), str.substring(1));
            }
        }
        if (cur.length() > 0)
            cur.deleteCharAt(cur.length() - 1);
    }
}
